1. Field of the Invention
The present invention relates to a method for allocating network resources. More specifically, the present invention relates to an efficient method for allocating network resources using heuristic method in WDM(Wavelength Division Multiplex) network required to be protected.
2. Description of the Related Art
In the real world, 1+1 or 1:1 protection mechanism commonly has been adopted. However, the resource utilization rate of those protection schemes is at most 50% low when applied to optical mesh networks. Thus, protection and restoration are important in designing reliable optical networks and have been widely studied in the literature.
With the rapid growth in popularity of the Internet, the data network is evolving to include a lot of bandwidth-intensive network applications. Optical technologies including wavelength-division multiplexing (WDM) are being researched as well as commercially deployed as technologies that can satisfy the bandwidth requirements of the Internet today and the foreknowable future. However, in the optical network, the high capacity of a link has the problem that a link failure can potentially lead to the loss of a large amount of data. So, we need to develop appropriate protection and restoration schemes which minimize the data loss when a link failure occurs. Essentially, there are two types of fault-recovery mechanisms. If backup resources (routes and wavelengths) are pre-computed and reserved in advance, we call it protection scheme. Otherwise, when a failure occurs, if another route and a free wavelength have to be discovered dynamically for each interrupted connection, we call it a restoration scheme. A restoration scheme is usually more resource-efficient, while a protection scheme has a faster recovery time and provides guaranteed recovery ability.
From the network topology perspective, protection schemes can be classified as ring protection and mesh protection. Both ring protection and mesh protection can be further divided into two groups: path protection and link protection.
In path protection, the traffic is rerouted through a link-disjoint backup route once a link failure occurs on its working path. In link protection, the traffic is rerouted only around the failed link. Path protection usually has less resource requirement and link protection usually has lower end-to-end propagation delay for the recovered route. In this study, we consider path protection in networks with mesh topology. FIG. 1 summarizes the classification of protection and restoration schemes.
Based on whether the sharing of network resources is allowed, a protection scheme can be categorized as dedicated protection or shared protection.
In dedicated protection, different protection paths do not share common resource, which may be a fiber line, a SONET channel, a WDM wavelength or a switch. Examples of dedicated protection are SONET 1+1 protection and SONET 1:1 protection. In SONET 1+1 protection, traffic is transmitted simultaneously on two separate fibers from the source to the destination. In SONET 1:1 protection, traffic is transmitted over only one fiber at a time. For dedicated protection, the failure and activation of one protection path doesn't affect any other protection path. The provisioning of this type of protection is relatively simple, and its behavior is deterministic.
On the other hand, in shared protection, multiple protection paths may go through common resources as illustrated in FIG. 2. In this example, the solid lines are primary paths and the dash lines are protection paths. The protection paths of primary path ab and cd share common nodes e and f as well as the link between these nodes. SONET 1:N protection is a special case of shared protection, since all primary paths have the same source and destination. In shared protection, when one protection path is activated, other protection paths that share common resources with it may have to be rerouted. For instance, when primary path ab in FIG. 2 fails, protection path aefb is activated, so the protection path cefd for primary path cd has to be rerouted. On the other hand, when a common resource fails, all protection paths that share that resource need to be rerouted. In the same example, if link ef fails, new protection paths of both primary paths need to be reestablished. Therefore, shared protection is more complex to provision and maintain. Shared protection does offer one advantage over dedicated protection, i.e., it may offer higher network utilization. Assume that every path needs protection. In the dedicated case, the best network utilization would be 50%. On the contrary, for shared protection, since multiple paths share common resources, the total number of resources required for all the protection paths can potentially be much lower. There are two ways of allocating backup capacity illustrated in FIG. 3. One is static allocation method. In the network design phase, a spare capacity allocation algorithm statically allocates spare capacities for known network flows to ensure their survivability. For these flows, solving the spare capacity allocation problem (SCAP) determines their backup path (BP) and the amount of spare capacity required on this path. So, static allocation method is NP-complete. Studies in [1] fall into this category. ([1]: S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks, part 1—protection,” Proc. IEEE INFOCOM'99, vol. 2, pp. 744-751, March 1999) Said [1] develops an integer linear program (ILP) formulation which is quite effective for small network. However, for large network, heuristic algorithms may be more suitable.
The other is dynamic reservation method. In the network operation phase, a survivability admission control algorithm (SACA) dynamically reserves backup capacity. The SACA determines whether the network can fulfill the survivability requirement of each channel request and make all admission accordingly. When an incoming channel request is admitted, the SACA reserves both working and backup capacities for this channel request. Two types of SACA are in use, first one is the state-independent SACA, and second one is the state-dependent SACA. State-independent SACA makes the channel admission decision based on fixed criteria that are predetermined before the channel establishment phase. Even though the state-independent SACA requires less network information and makes real-time decisions for survivability admission, this approach has two problems: first, it is difficult to decide the optimal values of critical parameters. Second, it cannot guarantee full restoration in a single link failure. On the other hand, state-dependent SACA makes channel admission based on network status information such as the usage of working and spare capacities on each link. It dynamically evaluates whether there is enough spare capacity for ensuring the survivability of an incoming channel request.
Currently, there are [2], [3], [4], and said mechanisms are more advanced. ([2]: S. Chen et al., “An effiecient spare capacity allocation strategy for ATM survivable networks”, Proc.GLOBECOM, 1996, vol. 1, pp. 442-46; [3]: L. Chen et al., “A survivability admission control mechanism for ATM networks,” Proc. GLOBECOM, 1998, vol. 2, pp. 1178-83; [4]: Chi-Chun Lo et al., “A novel approach of backup path reservation for survivable high-speed networks”, IEEE Communication Magazine, March 2003, pp. 146-52)
Said [2], [3], [4] will be described below;
S. Chen's algorithm [2] is in the category of state-independent SACA. As this algorithm is an approach of state-independent SACA, it has the limitations of state-independent SACA. L. Chen's algorithm [3] is in the category of state-dependent SACA. Although this algorithm overcomes the problems of state-independent SACA, it is considered only on a fully connected mesh network and causes excessive use of backup capacity. Currently, a mechanism proposed by Lo [4] made effort to enhance the drawbacks of the mechanisms on [2, 3]. However, the mechanism on [4] has remained several problems as follows:
first, in a viewpoint of algorithm, when preset link threshold is exceeded, only backup path is considered to exchange it for another backup path. It is partial way to improve total network utilization, expressed by number of blocked channel request and the number of used wavelengths for reserving working path and backup path, because the mechanism didn't regard working path when preset link threshold is exceeded. In addition, checking link threshold on the next step of deciding a best pair of working path and backup path all the time, and looking for another backup path instead of previously decided backup path by reason of excess of link threshold are complex work.
Second, in a viewpoint of performance evaluation method, evaluating the performance of mechanisms only by sharing rate in terms of backup capacity consumption is not relevant. Other valid evaluation method such as number of blocked channel request and wavelength consumption for reserving working and backup path should be considered.
Third, in the standpoint of simulation channel request bound, the paper [4] is very limited. Only single channel request is used for comparing the performance evaluation of mechanisms. Mechanisms should be simulated on the case of receiving various channel requests.
Last but not least, in the point of view of network utility, the network which consists of node with or without wavelength converter is not considered.
In this invention, most of problems pointed above are solved. Especially, we proposed two novel mechanism of reserving working path and backup path.
One is Advanced Combined Min-cost selection (ACM-selection), which is a variation of the combined min-cost selection mechanism on the paper [4]. We enhanced several drawbacks of the combined min-cost selection (CMC-selection) model by objective method, but the changes are not fundamental because ACM-selection mechanism maintains link threshold heuristic and traffic distribution mechanism working after the excess of link threshold. The changes are as follows:
first, in the CMC-selection one of working paths (WPs) in WP set is randomly selected for a WP, and link-disjoint backup paths (BPs) are considered to find a pair of WP and BP which consumes minimum wavelengths.
However, if we consider other WPs in the WP set, we are able to find a more proper pair of WP and BP which consume minimum wavelengths among all WP and BP pairs.
Second, it is possible to use traffic distribution function of CMC-selection, which is just used to find a new BP, in the initial WP and BP selection step. It happens to find several pairs of WP and BP, which consume same number of wavelengths. In this case, CMC-selection mechanism randomly chooses one of the pairs. However, ACM-selection mechanism uses traffic distribution function in the initial WP and BP selection step.
Third, in the CMC-selection mechanism WP is maintained when it finds a new BP because of the excess of link threshold. However, in the ACM-selection mechanism all WPs in the WPs are considered in the phase of finding a new BP by the reason of the excess of link threshold.
Fourth, weight-assigning method is used for reducing complexity of the mechanism. That is, when we find a pair of WP and BP in the first step, we confirm whether a link passed by BP exceeds preset link threshold, and if it exceeds, we give big weight cost.
In addition, we give weight by the number of required wavelengths for reserving WP and BP. So, we just sort the candidate pairs by the cost. It is very simple, but remarkably beneficial.
The following is the Random Selection (R-selection) mechanism used in general.
This is the commonly used model in the real world for protection and restoration. First, find shortest path for working path (WP) when randomly generated channel request is arrived at. Check the capacity of each link which WP passes by. If there is a link which has no enough capacity to allocate for WP, find another shortest path. The maximum number of iterations allowed in the step of finding WP is set to the number of shortest paths having same hop length. And then, find a link-disjoint backup path (BP). Also, the maximum number of iteration allowed in the step of finding BP is set to the number of link-disjoint BPs. If there are enough wavelengths for both WP and BP, accept channel request and allocate wavelengths. If not, reject channel request. FIG. 3.1 illustrates R-selection mechanism procedure.
And the following is the ACM-selection mechanism described shortly above, and improved from CMC-selection mechanism
Although we chose CMC-selection mechanism in order to compare with our proposed DAC-selection mechanism, we enhanced CMC-selection mechanism, which is called advanced combined min-cost selection (ACM-selection) mechanism, because of many drawbacks of the CMC-selection mechanism in [4]. In other words, some of drawbacks of CMC-selection mechanism can be improved objectively with small effort, but the original characteristics are not changed. We already introduced the differences between ACM-selection and CMC-selection mechanism. So, we describe ACM-selection mechanism itself here.
FIG. 5 is about common part of ACM-selection and DAC-selection. The difference of ACM-selection and DAC-selection mechanism is cost calculation heuristics. So, the cost functions of ACM-selection and DAC-selection are expressed differently.
Common features between said ACM-selection and the invention will be described in detailed description of embodiments, and the followings are related to different features.
Said different features are related a cost function. FIG. 6 is the cost function of ACM-selection mechanism.
The summation cost can be calculated as follow formula:Cost=(W1×SC+W2×(WC+BC)+W3×TC+W4×CC),where W1<<W2<<W3<<W4, a kind of priority or weight, and Wj is much bigger than Wi, where i<j and i={1, 2, 3} and j={2, 3, 4}
      SC    =                  (                              ∑                          i              ∈              BP                                ⁢                      R                          Sharing              i                                      )            Averag        ,SC (Sharing Cost) means average sharing rate cost of backup path. The goal of SC is to distribute channel request traffic into entire links of the network. So, it is possible to withdraw the load-balancing effect [4, 5, 6]. ([5]: Hongkyu Jeong et al., “A study on the resource utilization with various 1:1 protection policies on the optical networks”, in Proc. COOC2003, vol. 10, no. 1, pp. 119-120; [6]: Hongkyu Jeong et al., “Load-balancing in protection switching of optical networks”, COIN2003.)
The effect can fall down the number of blocked channel request and proper treatment when we think of double link failure, even though the double failure rarely happens. SC is calculated by above formula. First, add the sharing rate of each link used for BP, and divide it by the number of links. And then, average sharing rate can be obtained.
WC (Working path Cost) means the cost of reserving working path. That is, the cost is the same as the number of required wavelengths.
      BC    =                  min        j            ⁢              (                              BR            j                    -                      SBR            j                          )              ,      j    =    1    ,  …  ⁢          ,  W  ,where BRj is required number of wavelengths for BP reservation in the jth wavelength number, SBRj is the number of sharable wavelength for BP reservation in the jth wavelength number. Therefore, BC should find the wavelength number which consumes minimum wavelengths. BC (Backup path Cost) is the number of additionally required wavelengths. It means that sharable wavelengths are not counted in for the number of required wavelengths.
  TC  =            ∑              i        ∈        BP              ⁢          L              Exceeding        i            TC means threshold cost. LExceeding is 1 if number of wavelength used for previous channel requests exceeds preset link threshold, or 0 if otherwise. TC is the cost of the summation of the results after checking each link capacity allocation state. Therefore, if 3 links passed by a BP exceed link threshold, TC must be 3.
CC (Capacity Cost)=1 if there is no more wavelength to allocate on a link which WP and BP pass by. As the cost of CC is greatly big, the pair getting this cost should be the last candidate. Although this pair is selected to the best pair, this pair will not be accepted at the last step.
In conclusion of the cost function for ACM-selection, SC, WC, BC, TC, and CC are calculated and each cost is multiplied by each priority or weight. If we sum up all the costs, we can get total cost. Cost function block of ACM-selection mechanism is illustrated on FIG. 6.